a16z: Public Randomness and Randomness Beacons

Public randomness is an important component of many real-world security protocols. In some applications, such as gambling and multiplayer games, randomness adds fun. In other applications, randomness provides a fair way to allocate indivisible resources, from green cards, to the case distribution of judges in circuit courts, to the seeding of sports competitions. It is also used to allocate negative resources, such as tax audits or secondary airport security checks.

Traditionally, we rely on trusted institutions to generate randomness for these protocols, but in the Web3 world, we need to do better. In this article, we will explore the method of establishing publicly verifiable randomness through distributed random beacons, and then discuss some on-chain applications. (The second part will be released soon, focusing specifically on leader election, while providing an assessment of other leader election methods).

Generating random numbers is a well-known subtle task. For example, many cryptographic keys have been leaked because they rely on a problematic random number generator (Cloudflare’s wall of lava lamps can serve as a creative mitigation measure). However, this is just private randomness, where only one party needs to generate and use it.

In contrast, public randomness is a multi-party process, which greatly increases the difficulty. A good protocol for generating public randomness will have the following security properties:

1. Unbiased. No attacker or coalition of attackers can favor the output.
2. Reliable. No attacker can prevent the protocol from producing an output.
3. Verifiable. Anyone can easily verify the output of the protocol and should see the same output as others.
4. Unpredictable. If the protocol produces an output at time T1, no one can predict anything about the output at any time T0 < T1, with T0 being as close to T1 as possible.

Unbiasedness is a weaker property than unpredictability because any predictable protocol must be unbiased. Computer scientists would say that unbiasedness reduces to unpredictability because if you can bias, you can predict. However, sometimes we want to separate them for reasoning because they may rely on different assumptions, such as a dishonest majority may be able to predict the outcome but not bias it.

In addition to these properties, the protocol should be efficient to run and produce a large number of random bits. (In practice, it is usually sufficient for applications to generate 128 random bits, using them as a seed for a pseudorandom number generator PNRG to output more bits as needed. However, unpredictability should be maintained for each individual bit of the output to be used for applications such as lotteries or resource allocation). It is best if the protocol is also efficient in terms of communication and computational costs.

Different protocols may achieve these properties under different conditions. For example, some protocols may be unbiased against a coalition of any f1 malicious nodes, while being unpredictable against a coalition of any f2 < f1 malicious nodes. There are also varying degrees of bias. For example, in some protocols, a participant may be able to bias the output by “one bit” – meaning they can choose one of the two possible outputs. Other attacks may allow them to completely fix the output. However, in general, we do not want to tolerate any bias (or predictability) at all.

Cryptographers often start by thinking about the ideal solution to their problem. In the case of public randomness, a randomness beacon is an idealized service that regularly produces random outputs that meet all the necessary security requirements.

Such an idealized randomness beacon, like other cryptographic abstractions (such as random beacons or the universal group model), does not exist in the real world. However, it is a worthy goal and a useful model for reasoning about protocols that rely on public randomness.

We can consider several approximations of an ideal randomness beacon:

1. Centralized beacons. The simplest way to generate good randomness is through a centralized third-party service, such as the NIST randomness beacon or Random.org, which generates randomness from atmospheric noise and is recognized for use in gambling. This dependence on a third party completely undermines the concept of decentralization. In fact, in the examples above, we have to trust the relevant organizations to generate randomness correctly, without any cryptographic proof.

2. Physical randomness displays. Many traditional lotteries rely on public displays, which may include someone reaching into a container with ping pong balls with different numbers. Unfortunately, these are often easy to manipulate. For example, certain balls can be placed in the refrigerator and the selector can be told to pick the cold balls.

3. Natural beacons. A common idea is to use random natural phenomena, such as weather or cosmic background radiation, as a beacon. Unfortunately, all proposed sources do not provide strong consensus. Different observers will see slightly different values, which requires reintroducing a trusted party to make formal measurements, which has all the drawbacks of a centralized beacon.

4. Semi-centralized beacons. A better approach is to derive randomness directly from the Bitcoin block header or stock market closing prices, which are easier to publicly verify and difficult for any single party to